package Tu.Shizilianbiao;

/**
 * Created by Administrator on 2017/11/24/024.
 */
public class Shizilianbiao {
    int Numevertex; // 顶点个数
    int Numedges; // 边个数
    VertexNode[] vertexNodeList; // 顶点数组
    EdgeNode edgeNode;

    public Shizilianbiao(char[] vertex, char[][] edges) {
        Numevertex = vertex.length;
        Numedges = edges.length;

        // 初始化顶点,建立顶点表
        vertexNodeList = new VertexNode[Numevertex];
        for (int i = 0; i < Numevertex; i++) {
            vertexNodeList[i] = new VertexNode();
            vertexNodeList[i].vertex = vertex[i];
            vertexNodeList[i].firstIn = null;
            vertexNodeList[i].firstOut = null;
        }

        // 初始化边，利用头插法建立十字链表
        for (int i = 0; i < Numedges; i++) {
           EdgeNode edgeNode1 = new EdgeNode();
           EdgeNode edgeNode2 = new EdgeNode();
            int vi = getPosition(edges[i][0], vertex);
            int vj = getPosition(edges[i][1], vertex);

            edgeNode1.endvertex = vi;
            edgeNode1.firstvextex = vj;
            edgeNode1.endlink = vertexNodeList[vi].firstOut;
            vertexNodeList[vi].firstOut = edgeNode1;

            edgeNode2.endvertex = vi;
            edgeNode2.firstvextex = vj;
            edgeNode2.firstlink = vertexNodeList[vj].firstIn;
            vertexNodeList[vj].firstIn = edgeNode2;

        }
    }

    /*
     *  功能：顶点表结点结构
     *  参数：vertex 顶点域，存储顶点信息
     *       firstIn  入边表头指针，指向该顶点的入边表中第一个结点
     *       firstOut  出边表头指针，指向该顶点的出边表中第一个结点
     */
    private class VertexNode {
        char vertex;
        EdgeNode firstIn;
        EdgeNode firstOut;
    }

    /*
     *  功能：边表结点
     *  参数：endvertex  弧起点在顶点表的下标
     *        firstvextex  弧终点在顶点表的下标
     *        firstlink  入边表指针域,指向终点相同的下一条边
     *        endlink  出边表指针域，指向起点相同的下一条边
     */
    private class EdgeNode {
        int endvertex;
        int firstvextex;
        EdgeNode firstlink;
        EdgeNode endlink;
    }

    /**
     *  功能：返回ch位置
     */
    private int getPosition(char ch, char[] vexs) {
        for (int i = 0; i < Numevertex; i++)
            if (vexs[i] == ch)
                return i;
        return -1;
    }

    /*
     *  功能：打印邻接表和逆邻接表
     */
    public void print() {
        System.out.printf("领接表:\n");
        for (int i = 0; i < Numevertex; i++) {
            System.out.print(vertexNodeList[i].vertex + " ");
            if (vertexNodeList[i].firstOut != null) {
                EdgeNode EdgeNode2 = new EdgeNode();
                EdgeNode2 = vertexNodeList[i].firstOut;
                System.out.print(EdgeNode2.firstvextex);
                while (EdgeNode2.endlink != null) {
                    EdgeNode2 = EdgeNode2.endlink;
                    System.out.print(EdgeNode2.firstvextex);
                }
                System.out.print("\n");
            } else {
                System.out.print("\n");
            }
        }

        System.out.print("----------\n");

        System.out.printf("逆领接表:\n");
        for (int i = 0; i < Numevertex; i++) {
            System.out.print(vertexNodeList[i].vertex + " ");
            if (vertexNodeList[i].firstIn != null) {
                EdgeNode EdgeNode1 = new EdgeNode();
                EdgeNode1 = vertexNodeList[i].firstIn;
                System.out.print(EdgeNode1.endvertex);
                while (EdgeNode1.firstlink != null) {
                    EdgeNode1 = EdgeNode1.firstlink;
                    System.out.print(EdgeNode1.endvertex);
                }
                System.out.print("\n");
            } else {
                System.out.print("\n");
            }
        }
    }

    public static void main(String args[]) {
        // 顶点数组
        char[] vexs = {
                'A', 'B', 'C', 'D','E',
        };
        // 边数组
        char[][] edges = new char[][] {
                {'A', 'B'}, {'A', 'C'}, {'A', 'D'},
                {'B', 'D'}, {'C', 'D'},{'C','E'},
                {'B','E'}
        };

        OListDG listUDG = new OListDG(vexs, edges);
        listUDG.print();
    }
}
